Introduction

This book is a collection of all my notes from my degree (computer systems engineering).

It exists for a few purposes:

• To consolidate knowledge
• To aid revision
• To act as a reference during exams

Contributing

If you wish to contribute to this, either to make any additions or just to fix any mistakes I've made, feel free.

The sources are all available on my Github.

CS118

This section is mainly just a reference of some of the more detailed bits of the module. It assumes a pretty strong prior knowledge of object oriented programming so doesn't aim to be comprehensive, it just specifies some details to remember for the exam.

The version of Java on DCS systems at the time of writing is 11. This is also the version these notes refer to.

Useful Resources

• https://en.wikipedia.org/wiki/Single-precision_floating-point_format
• The Oracle documentation for specifics on how Java implements stuff

IEEE 754

IEEE 754 is a standardised way of storing floating point numbers with three components

• A sign bit
• A biased exponent
• A normalised mantissa

The examples below all refer to 32 bit numbers, but the principles apply to 64 bit.

• The exponent is an 8 bit unsigned number in biased form
  • To get the true exponent, subtract 127 from the binary value
• The mantissa is a binary fraction, with the first bit representing $1/2$, second bit $1/4$, etc.
  • The mantissa has an implicit $1.$, so 1 must always be added to the mantissa

Formula

$$-1^{sign}\times 2^{E-127}\times (1+\sum _{i=1}^{23}{b}_{23-i}{2}^{-i})$$

Decimal to Float

The number is converted to a binary fractional format, then adjusted to fit into the form we need. Take 12.375 for example:

• Integer part $(12{)}_{10}=(1100{)}_2$
• Fraction part $(0.375{)}_{10}=(0.011{)}_2$

Combining the two parts yields $1100.011$. However, the standard requires that the mantissa have an implicit 1, so it must be shifted to the right until the number is normalised (ie has only 1 as an integer part). This yields $(1.100011{)}_2$. As this has been shifted, it is actually $(1.100011{)}_2\times 2^3$. The three $(10)$ is therefore the exponent, but this has to be normalised (+127) to yield 130 $(10000010)$. The number is positive (sign bit zero) so this yields:

$$01000001010001100000000000000000$$

Float to Decimal

Starting with the value 0x41C80000 = 01000001110010000000000000000000:

• The exponent is 131, biasing (-127) gives 4
• The mantissa is 0.5625, adding 1 (normalising) gives 1.5625
• $2^4\times 1.5625$ gives 25

Special Values

• Zero
  • When both exponent and mantissa are zero, the number is zero
  • Can have both positive and negative zero
• Infinity
  • Exponent is all 1s, mantissa is zero
  • Can be either positive or negative
• Denormalised
  • If the exponent is all zeros but the mantissa is non-zero, then the value is a denormalised number
  • The mantissa does not have an assumed leading one
• NaN (Not a Number)
  • Exponent is all 1s, mantissa is non-zero
  • Represents error values

OOP Principles

Constructors

All Java classes have a constructor, which is the method called upon object instantiation.

• An object can have multiple overloaded constructors
• A constructor can have any access modifier
• Constructors can call other constructors through the this() method.
• If no constructor is specified, a default constructor is generated which takes no arguments and does nothing.
• The first call in any constructor is to the superclass constructor.
  • This can be elided, and the default constructor is called
    • If there is no default constructor, a constructor must be called explicitly
  • Can call explicitly with super()

Access Modifiers

Access modifiers apply to methods and member variables.

• private: only the members of the class can see
• public: anyone can see
• protected: only class and subclasses can see
• Default: package-private, only members of the same package can see

Inheritance

• To avoid the diamond/multiple inheritance problem, Java only allows for single inheritance
• This is done using the extends keyword in the class definition
• Inherits all public and protected methods and members
• Can, however, implement multiple interfaces

Example:

public class Car extends Vehicle implements Drivable, Crashable{
    // insert class body here
}

The Car class extends the Vehicle base class (can be abstract or concrete) and implements the behaviours defined by the interfaces Drivable and Crashable.

static

The static keyword defines a method, a field, or a block of code that belongs to the class instead of the object.

• Static fields share a mutable state accross all instances of the class
• Static methods are called from the class instead of from the object
• Static blocks are executed once, the first time the class is loaded into memory

Polymorphism

Polymorphism: of many forms. A broad term describing a few things in java.

Dynamic Polymorphism

An object is defined as polymorphic if it passes more than one instanceof checks. An object can be referred to as the type of any one of it's superclasses. Say for example there is a Tiger class, which subclasses Cat, which subclasses Animal, giving an inheritance chain of Animal <- Cat <- Tiger, then the following is valid:

Animal a = new Tiger();
Cat c = new Tiger();
Tiger t = new Tiger();

When referencing an object through one of it's superclass types, you can only call objects that the reference type implements. For example, if there was two methods, Cat::meow and Tiger::roar, then:

c.meow() //valid
t.meow() //valid
a.meow() //not valid - animal has no method meow
t.roar() //valid
c.roar() // not valid - cat has no method roar

Even though all these variables are of the same runtime type, they are being called from a reference of another type.

When calling a method of an object, the actual method run is the one that is furthest down the inheritance chain. This is dynamic/runtime dispatch.

public class Animal{
    public speak(){return "...";}
}

public class Dog extends Animal{
    public speak(){return "woof";}
}

public class Cat extends Animal{
    public speak(){return "meow";}
}

Animal a = new Animal();
Animal d = new Dog();
Animal c = new Cat();

a.speak() // "..."
d.speak() // "woof"
c.speak() // "meow"

Even though the reference was of type Animal, the actual method called was the overridden subclass method.

Static Polymorphism (Method Overloading)

Note: different to overridding

• Multiple methods with the same name can be written, as long as they have different parameter lists
• The method that is called depends upon the number of and type of the arguments passed

Example:

public class Addition{
    private int add(int x, int y){return x+y;}
    private float add(float x, float y){return x+y;}
    public static void main(String[] args){
        add(1,2); //calls first method
        add(3.14,2.72); //calls second method
        add(15,1.5); //calls second method
    }
}

Abstraction

Abstraction is the process of removing irrelevant details from the user, while exposing the relevant details. For example, you don't need to know how a function works, it's inner workings are abstracted away, leaving only the function's interface and details of what it does.

In the example below, the workings of the sine function are abstracted away, but we still know what it does and how to use it.

float sin(float x){
    //dont care really
}
sin(90); // 1.0

Encapsulation

Encapsulation is wrapping the data and the code that acts on it into a single unit. The process is also known as data hiding, because the data is often hidden (declared private) behind the methods that retrieve them (getters/setters).

Reference Variables

There is no such thing as an object variable in Java. Only primitives (int,char,float...), and references. All objects are heap-allocated (new), and a reference to them stored. Methods are all pass by value: either the value of the primitive, or the value of the reference. Java is not pass by reference . Objects are never copied/cloned/duplicated implicitly.

If a reference type is required (ie Integer), but a primitive is given ((int) 1), then the primitive will be autoboxed into it's equivalent object type.

Abstract Classes and Interfaces

• Abstract classes are classes that contain one or more abstract methods.
  • A class must be declared abstract
  • Abstract methods have no body, ie are unimplemented.
  • The idea of them is to generalise behaviour, and leave it up to subclasses to implement
  • Abstract classes cannot be instantiated directly, though can still have constructors for subclasses to call
• Interfaces are a special kind of class that contain only abstract methods (and fields declared public static final)
  • Used to define behaviour
  • Technically can contain methods, but they're default implementations
    • This raises all sorts of issues so is best avoided
  • Don't have to declare methods abstract, it's implicit

The diagram shows the inheritance hierarchy of the java collections framework, containing interfaces, abstract classes, and concrete classes.

Exceptions

Exceptions

Exceptions are events that occur within the normal flow of program execution that disrupt the normal flow of control.

Throwing Exceptions

Exceptions can occur when raised by other code we call, but an exception can also be raised manually using a throw statement. Any object that inherits, either directly or indirectly, from the Throwable class, can be raised as an exception.

//pop from a stack
public E pop(){
    if(this.size == 0)
        throw new EmptyStackException();
    //pop the item
}

Exception Handling

• Exceptions can be caught using a try-catch block
• If any code within the try block raises an exception, the catch block will be executed
  • catch blocks must specify the type of exception to catch
  • Can have multiple catch blocks for different exceptions
    • Only 1 catch block will be executed
• A finally block can be included to add any code to execute after the try-catch, regardless of if an exception is raised or not.
• The exception object can be queried through the variable e

try{
    //try to do something
} catch (ExceptionA e){
    //if an exception of type ExceptionA is thrown, this is executed
} catch (ExceptionB e){
    //if an exception of type ExceptionB is thrown, this is executed
} finally{
    //this is always executed
}

Exception Heirachy

• The Throwable class is the parent class of all errors and exceptions in Java
• There are two subclasses of Throwable
  • Error, which defines hard errors within the JVM that aren't really recoverable
  • Exception, which defines errors that may occur within the code
    • There are two kinds of exception, checked and unchecked

Checked and Unchecked Exceptions

• Checked exceptions must be either caught or re-thrown
  • IOException is a good example
• When a method that may throw a checked exception is required, there are two options
  • Wrap the possibly exception-raising code in a try-catch
  • Use the throws keyword in the method definition to indicate that the method may throw a checked exception

public static void ReadFile() throws FileNotFoundException{
    File f = new File("non-existant-file.txt")
    FileInputStream stream = new FileInputStream(f);
}
// OR
public static void ReadFile(){
    File f = new File("non-existant-file.txt")
    try{
        FileInputStream stream = new FileInputStream(f);
    } catch (FileNotFoundException){
        e.printStackTrace();
        return;
    }
}

• Unchecked Exceptions all subclass RunTimeException
  • ie NullPointerException and ArrayIndexOutOfBoundsException
• Can be thrown at any point and will cause program to exit if not caught

Custom Exceptions

• Custom exception classes can be created
• Should subclass Throwable
  • Ideally the most specific subclass possible
  • Subclassing Exception gives a new checked exception
  • Subclassing RunTimeException gives a new unchecked exception
• All methods such as printStackTrace and getMessage inherited from superclass
• Should provide at least one constructor that overrides a superclass constructor

public class IncorrectFileExtensionException
  extends RuntimeException {
    public IncorrectFileExtensionException(String errorMessage, Throwable err) {
        super(errorMessage, err);
    }
}

Generics

Generics allow for classes to be parametrised over some type or types, to provide additional compile time static type checking. A simple box class parametrised over some type E, for example:

public class Box<E>{
    E item;

    public Box(E item){
        this.item = item;
    }
    public E get(){
        return item;
    }
    public E set(E item){
        this.item = item;
    }
}

Generic Methods

Methods can be generic too, introducing their own type parameters. The parameters introduced in methods are local to that method, not the whole class. As an example, the static method below compares two Pair<K,V> classes to see if they are equal.

public static <K, V> boolean compare(Pair<K, V> p1, Pair<K, V> p2) {
        return p1.getKey().equals(p2.getKey()) &&
               p1.getValue().equals(p2.getValue());
    }

Type erasure

Type information in generic classes and methods is erased at runtime, with the compiler replacing all instances of the type variable with Object. Object is also what appears in the compiled bytecode. This means that at runtime, any type casting of generic types is unchecked, and can cause runtime exceptions.

CS126

The book Data Structures and Algorithms in Java by Goodrich, Tamassia and Goldwasser is a good resource as it aligns closely with the material. It can be found online fairly easily.

Arrays & Linked Lists

Arrays

Arrays are the most common data structure and are very versatile

• A sequenced collection of variables of the same type (homogenous)
• Each cell in the array has an index $\mathrm{0...}(n-1)$
• Arrays are of fixed length and so have a max capacity
• Can store primitives, or references to objects
• When inserting an element into the array, all to the right must be shifted up by one
• The same applies in reverse for removal to prevent null/0 gaps being left

Sorting Arrays

• The sorting problem:
  • Consider an array of unordered elements
  • We want to put them in a defined order
  • For example [3, 6, 2, 7, 8, 10, 22, 9] needs to become [2, 3, 6, 7, 8, 9, 10, 22]
• One possible solution: insertion sort:
  • Go over the entire array, inserting each element at it's proper location by shifting elements along

public static void insertionSort(int[] data){
    int n = data.length;
    for(int k = 1; k < n; k++){             //start with second element
        int cur = data[k];                  //insert data[k]
        int j = k;                          //get correct index j for cur
        while(j < 0 && data[j-1] > cur){    //data[j-1] must go after cur
            data[j] = data[j-1];            // slide data[j-1] to the right
            j--;                            //consider previous j for cur
        }
        data[j] = cur; //cur is in the right place
    }
}

• Insertion sort sucks
• Has worst case quadratic complexity, as k comparisons are required for k iterations.
• When the list is in reverse order (worst case), $\frac{n(n-1)}{2}$ comparisons are made
• Can do much better with alternative algorithms

Singly Linked Lists

• Linked lists is a concrete data structure consisting of a chain of nodes which point to each other
• Each node stores the element, and the location of the next node
• The data structure stores the head element and traverses the list by following the chain
• Operations on the head of the list (ie, prepending) are efficient, as the head node can be accessed via its pointer
• Operations on the tail require first traversing the entire list, so are slow
• Useful when data needs to always be accessed sequentially
• Generally, linked lists suck for literally every other reason

Doubly Linked Lists

• In a doubly linked list, each node stores a pointer to the node in front of and behind it
• This allows the list to be traversed in both directions, and for nodes to be easily inserted mid-sequence
• Sometimes, special header and trailer "sentinel" nodes are added to maintain a reference to the head an tail of the list
  • Also removes edge cases when inserting/deleting nodes as there is always nodes before/after head and tail

Analysis of Algorithms

This topic is key to literally every other one, and also seems to make up 90% of the exam questions (despite there being only 1 lecture on it) so it's very important.

• Need some way to characterise how good a data structure or algorithm is
• Most algorithms take input and generate output
• The run time of an algorithm typically grows with input size
• Average case is often difficult to determine
  • Focus on the worst case
• Runtime analysis and benchmarks can be used to determine the performance of an algorithm, but this is often not possible
  • Results will also vary from machine to machine
• Theoretical analysis is preferred as it gives a more high-level analysis
  • Characterises runtime as a function of input size $n$

Pseudocode

• Pseudocode is a high level description of an algorithm
• Primitive perations are assumed to take unit time
• For example
  • Evaluating an expression
  • Assigning to a variable
  • Indexing into an array
  • Calling a method

Looking at an algorithm, can count the number of operations in each step to analyse its runtime

public static double arrayMax(double[] data){
    int n = data.length; //2 ops
    double max = data[0]; //2 ops
    for (int j=1; j < n;j++) //2n ops
        if(data[j] > max) //2n-2 ops
            max = data[j]; //0 to 2n-2 ops
    return max; //1 op
}

• In the best case, there are $4n+3$ primitive operations
• In the worst case, $6n+1$
• The runtime $T(n)$ is therefore $a(4n+3)\le T(n)\le a(6n+1)$
  • $a$ is the time to execute a primitive operation

Functions

There are 7 important functions $f(n)$that appear often when analysing algorithms

• Constant - $1$
  • $f(n)=c$
  • A fixed constant
  • Could be any number but 1 is the most fundamental constant
  • Sometimes denoted $f(n)=c\times g(n)$ where $g(n)=1$
• Logarithmic - $\log n$
  • For some constant $b>1$, $f(n)={\log }_b(n)$
  • Logarithm is the inverse of the power function
    • $x={\log }_{b}n\iff b^x=n$
  • Usually, $b=2$ because we are computer scientists and everything is base 2
• Linear - $n$
  • $f(n)=cn$
    • $c$ is a fixed constant
• n-log-n - $n\log n$
  • $f(n)=n\times \log n$
  • Commonly appears with sorting algorithms
• Quadratic - $n^2$
  • $f(n)=n^2$
  • Commonly appears where there are nested loops
• Cubic - $n^3$
  • $f(n)=n^3$
  • Less common, also appears where there are 3 nested loops
  • Can be generalised to other polynomial functions
• Exponential - $2^n$
  • $f(n)=b^n$
    • $b$ is some arbitrary base, $n$ is the exponent

The growth rate of these functions is not affected by changing the hardware/software environment. Growth rate is also not affected by lower-order terms.

• Insertion sort takes time $\frac{1}{2}{n}^2$
  • Characterised as taking $n^2$ time
• Merge sort takes $2n\log n$
  • Characterised as $n\log n$
• The arrayMax example from earlier took $a(4n+3)\le T(n)\le a(6n+1)$ time
  • Characterised as $n$
• A polynomial $f(n)$ of degree $d$, is of order $n^d$

Big-O Notation

• Big-O notation is used to formalise the growth rate of functions, and hence describe the runtime of algorithms.
• Gives an upper bound on the growth rate of a function as $n\to \infty$
• The statement "$f(n)$ is $O(g(n))$" means that the growth rate of $f(n)$ is no more than the growth rate of $g(n)$
• If $f(n)$ is a polynomial of degree $d$, then $f(n)$ is $O(n^d)$
  • Drop lower order terms
  • Drop constant factors
• Always use the smallest possible class of functions
  • $2n$ is $O(n)$, not $O(n^2)$
• Always use the simplest expression
  • $3n+5$ is $O(n)$, not $O(3n)$

Formally, given functions $f(n)$ and $g(n)$, we say that $f(n)$ is $O(g(n))$ if there is a positive constant $c$ and a positive integer constant $n_0$, such that

$$f(n)\le cg(n)\text{for}n\ge n_0$$

where $c>0$, and $n_0\ge 1$

Examples

$2n+10$ is $O(n)$:

$$f(n)=2n+10,g(n)=n$$ $$2n+10\le cn$$ $$(c-2)n\ge 10$$ $$n\ge \frac{10}{c-2}$$ $$c=3,n_0=10$$

The function $n^2$ is not $O(n)$ $$f(n)=n^2,g(n)=n$$ $$n^2\le cn$$ $$n\le c$$ The inequality does not hold, since $c$ must be constant.

Big-O of $7n-2$: $$f(n)=7n-10,g(n)=n$$ $$7n-2\le cn$$ $$(c-7)n\ge 2$$ $$n\ge \frac{2}{c-7}$$ $$c=7,c_0=1$$

Big-O of $3n^3+20n^2+5$: $$f(n)=3n^3+20n^2+5,g(n)=n^3$$ $$3n^3+20n^2+5\le c{n}^3\text{for}n\ge n_0$$ $$c=4,n_0=21$$

$3\log n+5$ is $O(\log n)$ $$f(n)=3\log n+5,g(n)=\log n$$ $$3\log n+5\le c\log n\text{for}n\ge n_0$$ $$\log n\ge \frac{5}{c-3}$$ $$c=8,n_0=2$$

Asymptotic Analysis

• The asymptotic analysis of an algorithm determines the running time big-O notation
• To perform asymptotic analysis:
  • Find the worst-case number of primitive operations in the function
  • Express the function with big-O notation
• Since constant factors and lower-order terms are dropped, can disregard them when counting primitive operations

Example

The $i$th prefix average of an array $X$ is the average of the first $i+1$ elements of $X$. Two algorithms shown below are used to calculate the prefix average of an array.

Quadratic time

//returns an array where a[i] is the average of x[0]...x[i]
public static double[] prefixAverage(double[] x){
    int n = x.length;
    double[] a = new double[n];
    for(int j = 0; j < n; j++){
        double total = 0;
        for(int i = 0; i <= j; i++)
            total += x[i];
        a[j] = total / (j+1);
    }
    return a;
}

The runtime of this function is $O(1+2+...+n)+O(n)$. The sum of the first $n$ integers is $\frac{n^2+n}{2}$, so this algorithm runs in quadratic $O(n^2)$ time. This can easily be seen by the nested loops in the function too.

Linear time

//returns an array where a[i] is the average of x[0]...x[i]
public static double[] prefixAverage(double[] x){
    int n = x.length;
    double[] a = new double[n];
    double total = 0;
    for(int i = 0; i <= n; i++){
        total += x[i];
        a[i] = total / (i+1);
    }
    return a;
}

This algorithm uses a running average to compute the same array in linear time, by calculating a running sum.

Big-Omega and Big-Theta

Big-Omega is used to describe the best case runtime for an algorithm. Formally, $f(n)$ is $\Omega (g(n))$ if there is a constant $c>0$ and an integer constant $n_{0}geq1$ such that $$f(n)\ge c\cdot g(n)\text{for}n\ge n_0$$

Big-Theta describes the average case of the runtime. $f(n)$ is $\Theta (g(n))$ if there are constants $c^{\prime }>0$ and $c^{\prime \prime }>0$, and an integer constant $n_0\ge 1$ such that $$c^{\prime }g(n)\le f(n)\le c^{\prime \prime }g(n)\text{for}n\ge n_0$$

The three notations compare as follows:

• Big-O
  • $f(n)$ is $O(g(n))$ if $f(n)$ is asymptotically less than or equal to $g(n)$
• Big-$\Omega$
  • $f(n)$ is $\Omega (g(n))$ if $f(n)$ is asymptotically greater than or equal to $g(n)$
• Big-$\Theta$
  • $f(n)$ is $O(g(n))$ if $f(n)$ is asymptotically equal to $g(n)$

Recursive Algorithms

Recursion allows a problem to be broken down into sub-problems, defining a problem in terms of itself. Recursive methods work by calling themselves. As an example, take the factorial function:

$$n!=\{\begin{array}{ll}1& \text{if }n=0\\ n\times (n-1)!& \text{otherwise}\end{array}$$

In java, this can be written:

public static int factorial(int n){
    if(n == 0) return 1;
    return n * factorial(n-1);
}

Recursive algorithms have:

• A base case
  • This is the case where the method doesn't call itself, and the stack begins to unwind
  • Every possible chain of recursive calls must reach a base case
    • If not the method will recurse infinitely and cause an error
• A recursive case
  • Calls the current method again
  • Should always eventually end up on a base case

Binary Search

Binary search is a recursively defined searching algorithm, which works by splitting an array in half at each step. Note that for binary search, the array must already be ordered.

Three cases:

• If the target equals data[midpoint] then the target has been found
  • This is the base case
• If the target is less than data[midpoint] then we binary search everything to the left of the midpoint
• If the target is greater than data[midpoint] then we binary search everything to the right of the midpoint

public static boolean binarySearch(int[] data, int target, int left, int right){
    if (left > right)
        return false;
    int mid = (left + right) / 2;
    if(target == data[mid])
        return true;
    else if (target < data[mid])
        return binarySearch(data,target,low,mid-1);
    else
        return binarySearch(data,target,mid+1,high);

}

Binary search has $O(\log n)$, as the size of the data being processed halves at each recursive call. After the $i^{th}$ call, the size of the data is at most $n/2^i$.

Linear Recursion

• The method only makes one recursive call
• There may be multiple possible recursive calls, but only one should ever be made (ie binary search)
• For example, a method used in computing powers by repeated squaring:

$$pow(x,n)=\{\begin{array}{ll}1& \text{if }n=0\\ x{\left(pow(x,\frac{n-1}{2})\right)}^2& n\text{ is odd}\\ {\left(pow(x,\frac{n}{2})\right)}^2& n\text{ is even}\end{array}$$

public static int pow(int x, int n){
    if (n == 0) return 1;
    if (n % 2 == 0){
        y = pow(x,n/2);
        return x * y * y;
    }
    y = pow(x,(n-1)/2);
    return y * y;
}

Note how despite multiple cases, pow only ever calls itself once.

Binary Recursion

Binary recursive methods call themselves twice recursively. Fibonacci numbers are defined using binary recursion:

• $F_0$ = 0
• $F_1=1$
• $F_i=F_{i-1}+F_{i-2}$

public static int fib(int n){
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n-1) + fib(n-2);
}

This method calls itself twice, which isn't very efficient. It can end up having to compute the same result many many times. A better alternative is shown below, which uses linear recursion, and is therefore much much more efficient.

public static Pair<Integer,Integer> linearFib(int n){
    if(k = 1) return new Pair(n,0);
    Pair result = linearFib(n-1);
    return new Pair(result.snd+1, result.fst);
}

Multiple Recursion

Multiple recursive algorithms call themselves recursively more than twice. These are generally very inefficient and should be avoided.

Stacks & Queues

Abstract Data Types (ADTs)

• An ADT is an abstraction of a data structure
• Specifies the operations performed on the data
• Focus is on what the operation does, not how it does it
• Expressed in java with an interface

Stacks

• A stack is a last in, first out data structure (LIFO)
• Items can be pushed to or popped from the top
• Example uses include:
  • Undo sequence in a text editor
  • Chain of method calls in the JVM (method stack)
  • As auxillary storage in multiple algorithms

The Stack ADT

The main operations are push() and pop(), but others are included for usefulness

public interface Stack<E>{
    int size();
    boolean isEmpty();
    E peek(); //returns the top element without popping it
    void push(E elem); //adds elem to the top of the stack
    E pop(); //removes the top stack item and returns it
}

Example Implementation

The implementation below uses an array to implement the interface above. Only the important methods are included, the rest are omitted for brevity.

public class ArrayStack<E> implements Stack<E>{
    private E[] elems;
    private int top = -1;

    public ArrayStack(int capacity){
        elems = (E[]) new Object[capacity];
    }

    public E pop(){
        if (isEmpty()) return null;
        E t = elems[top];
        top = top-1;
        return t;
    }
    public E push(){
        if (top == elems.length-1) throw new FullStackException; //cant push to full stack
        top++;
        return elems[top];
    }
}

• Advantages
  • Performant, uses an array so directly indexes each element
  • $O(n)$ space and each operation runs in $O(1)$ time
• Disadvantages
  • Limited by array max size
  • Trying to push to full stack throws an exception

Queues

• Queues are a first in, first out (FIFO) data structure
• Insertions are to the rear and removals are from the front
  • In contrast to stacks which are LIFO
• Example uses:
  • Waiting list
  • Control access to shared resources (printer queue)
  • Round Robin Scheduling
    • A CPU has limited resources for running processes simultaneously
    • Allows for sharing of resources
    • Programs wait in the queue to take turns to execute
    • When done, move to the back of the queue again

The Queue ADT

public interface Queue<E>{
    int size();
    boolean isEmpty();
    E peek();
    void enqueue(E elem); //add to rear of queue
    E dequeue(); // pop from front of queue
}

Lists

The list ADT provides general support for adding and removing elements at arbitrary positions

The List ADT

public interface List<E>{
    int size();
    boolean isEmpty();
    E get(int i); //get the item from the index i
    E set(int i, E e); //set the index i to the element e, returning what used to be at that index
    E add(int i, E e); //insert an element in the list at index i
    void remove(int i); //remove the element from index i
}

Array Based Implementation (ArrayList)

Array lists are growable implementations of the List ADT that use arrays as the backing data structure. The idea is that as more elements are added, the array resizes itself to be bigger, as needed. Using an array makes implementing get() and set() easy, as they can both just be thin wrappers around array[] syntax.

• When inserting, room must be made for new elements by shifting other elements forward
  • Worst case (inserting to the head) $O(n)$ runtime
• When removing, need to shift elements backward to fill the hole
  • Same worst case as insertion, $O(n)$

When the array is full, we need to replace it with a larger one and copy over all the elements. When growing the array list, there are two possible strategies:

• Incremental
  • Increase the size by a constant $c$
• Doubling
  • Double the size each time

These two can be compared by analysing the amortised runtime of the push operation, ie the average time required $T(n)/n$ for a $n$ pushes taking a total time $T(n)$.

With incremental growth, over $n$ push operations, the array is replaced $k=n/c$ times, where $c$ is the constant amount the array size is increased by. The total time $T(n)$ of $n$ push operations is proportional to: $$c+2c+3c+...+kc=c(1+2+..+k)=\frac{ck(k+1)}{2}$$

Since $c$ is a constant, $T(n)$ is $\Omega (k^2)$, meaning the amortised time of a push operation is $\Omega (n)$.

With doubling growth, the array is replaced $k={\log }_{2}n$ times. The total time $T(n)$ of $n$ pushes is proportional to:

$$1+2+4+8+...+2^k=2^{k+1}-1=2n-1$$

Thus, $T(n)$ is $O(n)$, meaning the amortised time $T(n)/n$ is $O(1)$

Positional Lists

• Positional lists are a general abstraction of a sequence of elements without indices
• A position acts as a token or marker within the broader positional list
• A position p is unaffected by changes elsewhere in a list
  • It only becomes invalid if explicitly deleted
• A position instance is an object (ie there is some Position class)
  • ie p.getElement() returns the element stored at position p
• A very natural way to implement a positional list is with a doubly linked list, where each node represents a position.
  • Where a pointer to a node exists, access to the previous and next node is fast ($O(1)$)

ADT

public interface PositionalList<E>{
    int size();
    boolean isEmpty();
    Position<E> first(); //return postition of first element
    Position<E> last();  //return position of last element
    Position<E> before(Position<E> p); //return position of element before position p
    Position<E> after(Posittion<E> p); //return position of element after position p
    void addFirst(E e); //add a new element to the front of the list
    void addLast(E e); // add a new element to the back of the list
    void addBefore(Position<E> p, E e); // add a new element just before position p
    void addAfter(Position<E> p, E e); // add a new element just after position p
    void set(Position<E> p, E e); // replaces the element at position p with element e
    E remove(p); //removes and returns the element at position p, invalidating the position
}

Iterators

Iterators are a software design pattern that abstract the process of scanning through a sequence one element at a time. A collection is Iterable if it has an iterator() method, which returns an instance of a class which implements the Iterator interface. Each call to iterator() returns a new object. The iterable interface is shown below.

public interface Iterator<E>{
    boolean hasNext(); //returns true if there is at least one additional element in the sequence
    E next(); //returns the next element in the sequence, advances the iterator by 1 position.
}
// example usage
public static void iteratorOver(Iterable<E> collection){
    Iterator<E> iter = collection.iterator();
    while(iter.hasNext()){
      E var = iter.next();
      System.out.println(var);
    }
}

Maps

• Maps are a searchable collection of key-value entries
• Lookup the value using the key
• Keys are unique

The Map ADT

public interface Map<K,V>{
    int size();
    boolean isEmpty();
    V get(K key); //return the value associated with key in the map, or null if it doesn't exist
    void put(K key, V value); //associate the value with the key in the map
    void remove(K key); //remove the key and it's value from the map
    Collection<E> entrySet(); //return an iterable collection of the values in the map
    Collection<E> keySet(); //return an iterable collection of the keys in the map
    Iterator<E> values(); //return an iterator over the map's values
}

List-Based Map

A basic map can be implemented using an unsorted list.

• get(k)
  • Does a simple linear search of the list looking for the key,value pair
  • Returns null if search reaches end of list and is unsuccessful
• put(k,v)
  • Does linear search of the list to see if key already exists
    • If so, replace value
  • If not, just add new entry to end
• remove(k)
  • Does a linear search of the list to find the entry and removes it
• All operations take $O(n)$ time so this is not very efficient

Hash Tables

• Recall the map ADT
• Intuitively, a map M supports the abstraction of using keys as indices such as M[k]
• A map with n keys that are known to be integers in a fixed range is just an array
• A hash function can map general keys (ie not integers) to corresponding indices in a table/array

Hash Functions

A hash function $h$ maps keys of a given type to integers in a fixed interval $[0,N-1]$.

• A very simple hash function is the mod function: $h(x)=x\mathrm{mod}N$

  • Works for integer keys
  • The integer $h(x)$ is the hash value of the key $x$

• The goal of a hash function is to store an entry $(k,v)$ at index $i=h(k)$

• Function usually has two components:

  • Hash code $h_1$
    • keys -> integers
  • Compression function $h_2$
    • integers -> integers in range $[0,N-1]$
  • Hash code applied first, then compression - $h(x)=h_2(h_1(x))$ Some example hash functions:

• Memory address

  • Use the memory address of the object as it's hash code

• Integer cast

  • Interpret the bits of the key as an integer
  • Only suitable with $\le$ 64 bits

• Component sum

  • Partition they key into bitwise components of fixed length and sum the components

• Polynomial accumulation

  • Partition the bits of the key into a sequence of components of fixed length $a_0$, $a_1$, ... , $a_{n-1}$
  • Evaluate the polynomial $P(z)=a_0+a_{1}z+a_2{z}^2+...+a_{n-1}{z}^{n-1}$ for some fixed value $z$
  • Especially suitable for strings
  • Polynomial can be evaluated in $O(n)$ time as $p_i(z)=a_{n-i-1}+z{p}_{i-1}(z)$

Some example compression functions:

• Division
  • $h_2(y)=y\mathrm{mod}N$
  • The size $N$ is usually chosen to be a prime to increase performance
• Multiply, Add, and Divide (MAD)
  • $h_2(y)=(ay+b)modN$
  • $a$ and $b$ are nonnegative integers such that $a\mathrm{mod}N\ne 0$

Collision Handling

Collisions occur when different keys hash to the same cell. There are several strategies for resolving collisions.

Separate Chaining

With separate chaining, each cell in the map points to another map containing all the entries for that cell.

Linear Probing

• Open addressing
  • The colliding item is placed in a different cell of the table
• Linear probing handles collisions by placing the colliding item at the next available table cell
• Each table cell inspected is referred to as a "probe"
• Colliding items can lump together, causing future collisions to cause a longer sequence of probes

Consider a hash table $A$ that uses linear probing.

• get(k)
  • Start at cell $h(k)$
  • Prove consecutive locations until either
    • Key is found
    • Empty cell is found
    • All cells have been unsuccessfully probed
• To handle insertions and deletions, need to introduce a special marker object defunct which replaces deleted elements
• remove(k)
  • Search for an entry with key k
  • If an entry (k, v) is found, replace it with defunct and return v
  • Else, return null

Double Hashing

• Double hashing uses two hash functions h() and f()
• If cell h(k) already occupied, tries sequentially the cell $(h(k)+i\cdot f(k))\mathrm{mod}N$ for $i=1,2,\mathrm{3...}$
• f(k) cannot return zero
• Table size $N$ must be a prime to allow probing of all cells
• Common choice of second hash func is $f(k)=q-k\mathrm{mod}q$ where q is a prime
• if $f(k)=1$ then we have linear probing

Performance

• In the worst case, operations on hash tables take $O(n)$ time when the table is full and all keys collide into a single cell
• The load factor $\alpha =n/N$ affects the performance of a hash table
  • $n$ = number of entries
  • $N$ = number of cells
• When $\alpha$ is large, collision is likely
• Assuming hash values are true random numbers, the "expected number" of probes for an insertion with open addressing is $\frac{1}{1-\alpha }$
• However, in practice, hashing is very fast and operations have $O(1)$ performance, provided $\alpha$ is not close to 1

Sets

A set is an unordered collection of unique elements, typically with support for efficient membership tests

• Like keys of a map, but with no associated value

Set ADT

Sets also provide for traditional mathematical set operations: Union, Intersection, and Subtraction/Difference.

public interface Set<E>{
    void add(E e); //add element e to set if not already present
    void remove(E e); //remove element e from set if present
    boolean contains(E e); //test if element e is in set
    Iterator<E> iterator(); //returns an iterator over the elements
    //updates the set to include all elements of set T
    // union
    void addAll(Set<E> T);
    //updates the set to include only the elements of the set that are also in T
    //intersection
    void retainAll(Set<E> T);
    //updates the set to remove any elements that are also in T
    //difference
    void removeAll(Set<E> T);
}

Generic Merging

Generic merge is a generalised merge of two sorted lists A and B to implement set operations. Uses a template method merge and 3 auxillary methods that describe what happens in each case:

• aIsLess
  • Called when the element of A is less than the element of B
• bIsLess
  • Called when the element of B is less than the element of A
• bothEqual
  • Called when the element of A is equal to the element of B

public static Set<E> merge(Set<E> A, Set<E> B){
    Set<E> S = new Set<>();
    while (!A.isEmpty() && !B.isEmpty()){
        a = A.firstElement();
        b = B.firstElement();
        if(a < b){
            aIsLess(a,S);
            A.remove(a);
        }
        else if (b < a){
            bIsLess(b,S);
            B.remove(b);
        }
        else{ //b == a
            bothEqual(a,b,S);
            A.remove(a);
            B.remove(b);
        }
        while(!A.isEmpty()){
            aIsLess(a,S);
            A.remove(a);
        }
        while(!B.isEmpty()){
            bIsLess(b,S);
            B.remove(b);
        }
    }
    return S;
}

• Any set operation can be implemented using generic merge
• Union
  • aIsLess adds a into S
  • bIsLess adds b into S
  • bothEqual adds a (or b) into S
• Intersection
  • aIsLess and bIsLess do nothing
  • bothEqual adds a (or b) into S
• Difference
  • aIsLess adds a into S
  • bIsLess and bothEqual do nothing
• Runs in linear time, $O(N_A+N_B)$, provided the auxillary methods are $O(1)$

Trees

• A tree is an abstract model of a heirarchical structure
• A tree consists of nodes with a parent-child relationship
  • A parent has one or more children
  • Each child has only one parent
• The root is the top node in the tree, the only node without a parent
• An internal node has at least one child
• An external node (or leaf) is a mode with no children
• Nodes have ancestors (ie, the parent node of a parent)
• The depth of a node is its number of ancestors
• The height of a tree is its maximum depth

Tree ADT

Tree ADTs are defined using a similar concept to positional lists, as they don't have a natural ordering/indexing in the same way arrays do.

public interface Tree<E>{
    int size();
    boolean isEmpty();
    Node<E> root(); //returns root node
    Node<E> parent(Node<E> n); //returns parent of Node n
    Iterable<Node<E>> children(Node<E> n); //collection of all the children of Node n
    int numChildren(Node<E> n);
    Iterator<E> iterator(); //an iterator over the trees elements
    Iterator<Node<E>> nodes(); //collection of all the nodes
    boolean isInternal(Node<E> n); //does the node have at least one child
    boolean isExternal(Node<E> n); //does the node have no children
    boolean isRoot(Node<E> n); //is the node the root

}

Tree Traversal

Trees can be traversed in 3 different orders. As trees are recursive data structures, all 3 traversals are defined recursively. The tree below is used as an example in all 3 cases.

Pre-order

• Visit the root
• Pre order traverse the left subtree
• Pre order traverse the right subtree

Pre-order traversal of the tree gives: F B A D C E G I H

In-order

• In order traverse the left subtree
• Visit the root
• In order traverse the right subtree

In-order traversal of the tree gives: A B C D E F G H I

Post-order

• Post order traverse the left subtree
• Post order traverse the right subtree
• Visit the root

Post-order traversal of the tree gives: A C E D B H I G F

Binary Trees

A binary tree is a special case of a tree:

• Each node has at most two children (either 0, 1 or 2)
• The children of the node are an ordered pair (the left node is less than the right node)

A binary tree will always fulfil the following properties:

• $e=i+1$
• $n=2e-1$
• $h\le i$
• $h\le (n-1)/2$
• $e\le 2^h$
• $h\ge {\log }_{2}e$
• $h\ge {\log }_2(n+1)-1$

Where:

• $n$ is the number of nodes in the tree
• $e$ is the number of external nodes
• $i$ is the number of internal nodes
• $h$ is the height/max depth of the tree

Binary Tree ADT

The binary tree ADT is an extension of the normal tree ADT with extra accessor methods.

public interface BinaryTree<E> extends Tree<E>{
    Node<E> left(Node<E> n); //returns the left child of n
    Node<E> right(Node<E> n); //returns the right child of n
    Node<E> sibling(Node<E> n); //returns the sibling of n
}

Arithmetic Expression Trees

Binary trees can be used to represent arithmetic expressions, with internal nodes as operators and external nodes as operands. The tree below shows the expression $(2\times (a-1))+(3\times b)$. Traversing the tree in-order will can be used to print the expression infix, and post-order evaluating each node with it's children as the operand will return the value of the expression.

Implementations

• Binary trees can be represented in a linked structure, similar to a linked list
• Node objects are positions in a tree, the same as positions in a positional list
• Each node is represented by an object that stores
  • The element
  • A pointer to the parent node
  • A pointer to the left child node
  • A pointer to the right child node
• Alternatively, the tree can be stored in an array A
• A[root] is 0
• If p is the left child of q, A[p] = 2 * A[q] + 1
• If p is the right child of q, A[p] = 2 * A[q] + 2
• In the worst, case the array will have size $2^n-1$

Binary Search Trees

• Binary trees can be used to implement a sorted map
• Items are stored in order by their keys
• For a node $p$ with key $K_p$, every key in the left subtree is less than $K_p$, and every node in the right subtree is greater than $K_p$
• This allows for support of nearest-neighbour queries, so can fetch the key above or below another key
• Binary search can perform nearest neighbour queries on an ordered map to find a key in $O(\log n)$ time
• A search table is an ordered map implemented using a sorted sequence
  • Searches take $O(\log n)time$
  • Insertion and removal take $O(n)$ time
  • Only effective for maps of small size

Methods

Binary trees are recursively defined, so all the methods operating on them are easily defined recursively also.

• Search
• To search for a key $K$
  • Compare it with the key at $K_{root}$
  • If $K_{root}=K$, the value has been found
  • If $K_{root}<K$, search the right subtree
  • If $K_{root}>K$, search the left subtree
• Insertion
  • Search for the key being inserted $K$
  • Insert $K$ at the leaf reached by the search
• Deletion
  • Find the internal node that is follows the key being inserted in an in order traversal (the in order successor)
  • Copy key into the in order successor node
  • Remove the node copied out of

Performance

• Consider a binary search tree with $n$ items and height $h$
• The space used is $O(n)$
• The methods get, put, remove take $O(h)$ time
  • The height h is $O(\log n)$ in the best case, when the tree is perfectly balanced
  • In the worst case, when the tree is basically just a linked list, this decays to $O(n)$

AVL Trees

• AVL trees are balanced binary trees
  • For every internal node $v$ of the tree, the heights of the subtrees of $v$ can differ by at most 1
• The height of an AVL tree storing $n$ keys is $O(\log n)$
• Balance is maintained by rotating nodes every time a new one is inserted/removed

Performance

• The runtime of a single rotation is $O(1)$
• The tree is assured to always have $h=\log n$, so the runtime of all methods is $O(\log n)$
• This makes AVL trees an efficient implementation of binary trees, as their performance does not decay as the tree becomes unbalanced

Priority Queues

A priority queue is an implementation of a queue where each item stored has a priority. The items with the highest priority are moved to the front of the queue to leave first. A priority queue takes a key along with a value, where the key is used as the priority of the item.

Priority Queue ADT

public interface PriorityQueue<K,V>{
    int size();
    boolean isEmpty();
    void insert(K key, V value); //inserts a value into the queue with key as its priority
    V removeMin(); //removes the entry with the lowest key (at the front of the queue)
    V min(); //returns but not removes the smallest key entry (peek)
}

Entry Objects

• To store a key-value pair, a tuple/pair-like object is needed
• An Entry<K,V> object is used to store each queue item
  • Key is what is used to defined the priority of the item in the queue
  • Value is the queue item
• This pattern is similar to what is used in maps

public class Entry<K,V>{
    private K key;
    private V value;

    public Entry(K key, V value){
        this.key = key;
        this.value = value;
    }

    public K getKey(){
        return key;
    }

    public V getValue(){
        return value;
    }

}

Total Order Relations

• Keys may be arbitrary values, so they must have some order defined on them
  • Two entries may also have the same key
• A total order relation is a mathematical concept which formalises ordering on a set of objects where any 2 are comparable.
• A total ordering satisfies the following properties $\forall a,b,c\in X$
  • $a\le b$ or $b\le a$
    • Comparability property
  • If $a\le b$ $b\le c$, then $a\le c$
    • Transitive property
  • If $a\le b$ and $b\le a$, then $a=b$
    • Antisymmetric property
  • $a\le a$
    • Reflexive property

Comparators

• A comparator encapsulates the action of comparing two objects with a total order declared on them
• A priority queue uses a comparator object given to it to compare two keys to decide their priority

public class Comparator<E>{
    public int compare(E a, E b){
        if(a < b)
            return -1;
        if(a > b)
            return 1;
        return 0;
    }
}

Implementations

Unsorted List-Based Implementation

A simple implementation of a priority queue can use an unsorted list

• insert() just appends the Entry(key,value) to the list
  • $O(1)$ time
• removeMin() and min() linear search the list to find the smallest key (one with highest priority) to return
  • Linear search takes $O(n)$ time

Sorted List-Based Implementation

To improve the speed of removing items, a sorted list can instead be used. These two implementations have a tradeoff between which operations are faster, so the best one for the application is usually chosen.

• insert() finds the correct place to insert the Entry(key,value) in the list to maintain the ordering
  • Has to find place to insert, takes $O(n)$ time
• As the list is maintained in order, the entry with the lowest key is always at the front, meaning removeMin() and min() just pop from the front
  • Takes $O(1)$ time

Sorting Using a Priority Queue

The idea of using a priority queue for sorting is that all the elements are inserted into the queue, then removed one at a time such that they are in order

• Selection sort uses an unsorted queue
  • Inserting $n$ items in each $O(1)$ time takes $O(n)$ time
  • Removing the elements in order
    • $O(n)+O(n-1)+O(n-2)+...+O(1)$
  • Overall $O(n^2)$ time
• Insertion sort uses a sorted queue
  • Runtimes are the opposite to unsorted
  • Adding $n$ elements takes $O(1)+O(2)+O(3)+...+O(n)$ time
  • Removing $n$ elements in each $O(1)$ time takes $O(n)$ time
  • Overall runtime of $O(n^2)$ again

Heaps

• A heap is a tree-based data structure where the tree is a complete binary tree
• Two kinds of heaps, min-heaps and max-heaps
• For a min-heap, the heap order specifies that for every internal node $v$ other than the root, $v\ge parent(v)$
  • In other words, the root of the tree/subtree must be the smallest node
  • This property is inverted for max heaps
• Complete binary tree means that every level of the tree, except possibly the last, is filled, and all nodes are as far left as possible.
  • More formally, for a heap of height $h$, for $i=0,1,...,h-1$ there are $2^i$ nodes of depth $i$
  • At depth $h-1$, the internal nodes are to the left of the external nodes
  • The last node of a heap is the rightmost node of maximum depth
• Unlike binary search trees, heaps can contain duplicates
• Heaps are also unordered data structures
• Heaps can be used to implement priority queues
  • An Entry(Key,Value) is stored at each node

Insertion

• To insert a node z into a heap, you insert the node after the last node, making z the new last node
  • The last node of a heap is the rightmost node of max depth
• The heap property is then restored using the upheap algorithm
• The just inserted node is filtered up the heap to restore the ordering
• Moving up the branches starting from the z
  • While parent(z) > (z)
    • Swap z and parent(z)
• Since a heap has height $\log n$, this runs in $O(\log n)$ time

Removal

• To remove a node z from the heap, replace the root node with the last node w
• Remove the last node w
• Restore the heap order using downheap
• Filter the replacement node back down the tree
  • While w is greater than either of its children
    • Swap w with the smallest of its children
• Also runs in $O(\log n)$ time

Heap Sort

For a sequence S of n elements with a total order relation on them, they can be ordered using a heap.

• Insert all the elements into the heap
• Remove them all from the heap again, they should come out in order
• $n$ calls of insert take $O(n\log n)$ time
• $n$ calls to remove take $O(n\log n)$ time
• Overall runtime is $O(n\log n)$
• Much faster than quadratic sorting algorithms such as insertion and selection sort

Array-based Implementation

For a heap with n elements, the element at position p is stored at cell f(p) such that

• If p is the root, f(p) = 0
• If p is the left child q, f(p) = 2*f(q)+1
• If p is the right child q, f(p) = 2*f(q)+2

Insert corresponds to inserting at the first free cell, and remove corresponds to removing from cell 0

• A heap with n keys has length $O(n)$

Skip Lists

• When implementing sets, the idea is to be able to test for membership and update elements efficiently
• A sorted array or list is easy to search, but difficult to maintain in order
• Skip lists consists of multiple lists/sets
  • The skip list $S=\left\{S_0,S_1,S_2,...,S_h\right\}$
  • $S_0$ contains all the elements, plus $\pm \infty$
  • $S_i$ is a random subset of $S_{i-1}$, for $i=1,2,...,h-1$
    • Each element of $S_{i-1}$ appears in $S_i$ with probability 0.5
  • $S_h$ contains only $\pm \infty$

Search

To search for an element $x$ in the list:

• Start in the first position of the top list
• At the current position $p$, compare $x$ with the next element in the current list $y$
  • If $x=y$, return $y$
  • If $x>y$, move to the next element in the list
    • "Scan forward"
  • If $x<y$, drop down to the element below
    • "Drop down"
• If the end of the list ($+\infty$) is reached, the element does not exist

Insertion

To insert an element $k$ into the list:

• Repeatedly toss a fair coin until tails comes up
  • $i$ is the number of times the coin came up heads
• If $i\ge h$, add to the skip list new lists $S_{h+1},...,S_{i+1}$
  • Each containing only the two end keys $\pm \infty$
• Search for $k$ and find the positions $p_0,p_1,...,P_i$ of the items with the largest element $>k$ in each list $S_0,S_1,...,S_i$
  • Same as the search algorithm
• For $j=\mathrm{0..}i$, insert k into list $S_j$ after position $p_j$

Deletion

To remove an entry $x$ from a skip list:

• Search for $x$ in the skip list and find the positions of the items $p_0,p_1,...,p_i$ containing $x$
• Remove those positions from the lists $S_0,S_1,...,S_i$
• Remove a list if neccessary

Implementation

A skip list can be implemented using quad-nodes, where each node stores

• It's item/element
• A pointer to the node above
• A pointer to the node below
• A pointer to the next node
• A pointer to the previous node

Performance

• The space used by a skip list depends on the random number on each invocation of the insertion algorithm
  • On average, the expected space usage of a skip list with $n$ items is $O(n)$
• The run time of the insertion is affected by the height $h$ of the skip list
  • A skip list with $n$ items has average height $O(\log n)$
• The search time in a skip list is proportional to the number of steps taken
• The drop-down steps are bounded by the height of the list
• The scan-forward steps are bounded by the length of the list
  • Both are $O(\log n)$
• Insertion and deletion are also both $O(\log n)$

Graphs

A graph is a collection of edges and vertices, a pair $(V,E)$, where

• $V$ is a set of nodes, called vertices
• $E$ is a collection of pairs of vertices, called edges
• Vertices and edges are positions and store elements

Examples of graphs include routes between locations, users of a social network and their friendships, and the internet.

There are a number of different types of edge in a graph, depending upon what the edge represents:

• Directed edge
  • Ordered pair of vertices $(u,v)$
  • First vertex $u$ is the origin
  • Second vertex $v$ is the destination
  • For example, a journey between two points
• Undirected edge
  • Unordered pair of vertices $(u,v)$
• In a directed graph, all edges are directed
• In an undirected graph, all edged are undirected

Graph Terminology

• Adjacent vertices
  • Two vertices $U$ and $V$ are adjacent (ie connected by an edge)
• Edges incident on a vertex
  • The edges connect to a vertex
  • $a$, $d$, and $b$ are incident on $V$
• End vertices or endpoints of an edge
  • The vertices connected to an edge
  • $U$ and $V$ are endpoints of $a$
• The degree of a vertex
  • The number of edges connected to it
  • $X$ has degree 5
• Parallel edges
  • Edges that make the same connection
  • $h$ and $i$ are parallel
• Self-loop
  • An edge that has the same vertex at both ends
  • $j$ is a self-loop
• Path
  • A sequence of alternating vertices and edges
  • Begins and ends with a vertex
  • Each edge is preceded and followed by its endpoints
  • $P_1=(V,b,X,h,Z)$ is a simple path
• Cycle
  • A circular sequence of alternating vertices and edges
    • A circular path
  • A simple cycle is one where all edges and vertices are distinct
  • A non-simple cycle contains an edge or vertex more than once
  • A graph without cycles (acyclic) is a tree
• Length
  • The number of edges in a path
  • The number of edges in a cycle

Graph Properties

Notation:

• $n$ is the number of vertices
• $m$ is the number of edges
• $\mathrm{deg}(v)$ is the degree of vertex $v$

The sum of the degrees of the vertices of a graph is always an even number. Each edge is counted twice, as it connects to two vertices, so ${\sum }_v\mathrm{deg}(v)=2m$. For example, the graph shown has $n=4$ and $m=6$. $\mathrm{deg}(v)=3\Rightarrow {\sum }_v\mathrm{deg}(v)=2m=12$

In an undirected graph with no self loops and no multiple edges, $m\le n\frac{n-1}{2}$. Each vertex has degree at most $(n-1)$ and ${\sum }_v\mathrm{deg}(v)=2m$. For the graph shown, $m=6\le n\frac{n-1}{2}=6$

The Graph ADT

A graph is a collection of vertices and edges, which are modelled as a combination of 3 data types: Vertex, Edge and Graph.

• A Vertex is just a box object storing an element provided by the user
• An Edge also stores an associated value which can be retrieved

public interface Graph{
    int numVertices();

    Collection vertices(); //returns all the graph's vertices

    int numEdges();

    Collection<Edge> edges(); //returns all the graph's edges

    Edge getEdge(u,v); //returns the edge between u and v, if on exists
    // for an undirected graph getEdge(u,v) == getEdge(v,u)

    Pair<Vertex, Vertex> endVertices(e); //returns the endpoint vertices of edge e

    Vertex oppsite(v,e); //returns the vertex adjacent to v along edge e

    int outDegree(v); //returns the number of edges going out of v

    int inDegree(v); //returns the number of edges coming into v
    //for an undirected graph, inDegree(v) == outDegree(v)

    Collection<Vertex> outgoingEdges(v); //returns all edges that point out of vertex v

    Collection<Vertex> incomingEdges(v); //returns all edges that point into vertex v
    //for an undirected graph, incomingEdges(v) == outgoingEdges(v)

    Vertex insertVertex(x); //creates and returns a new vertex storing element x

    Edge insertEdge(u,v,x); //creates and returns a new edge from vertices u to v, storing element x in the edge

    void removeVertex(v); //removes vertex v and all incident edges from the graph

    void removeEdge(e); //removes edge e from the graph
}

Representations

There are many different ways to represent a graph in memory.

Edge List

An edge list is just a list of edges, where each edge knows which two vertices it points to.

• The Edge object stores
  • It's element
  • It's origin Vertex
  • It's destination Vertex
• The edge list stores a sequence of Edge objects

Adjacency List

In an adjacency list, each vertex stores an array of the vertices adjacent to it.

• The Vertex object stores
  • It's element
  • A collection/array of all it's incident edges
• The adjacency list stores all Vertex Objects

Adjacency Matrix

An adjacency matrix is an $n\times n$ matrix, where $n$ is the number of vertices in the graph. It acts as a lookup table, where each cell corresponds to an edge between two vertices.

• If there is an edge between two vertices $u$ and $v$, the matrix cell $(u,v)$ will contain the edge.
• Undirected graphs are symmetrical along the leading diagonal

Subgraphs

• A subgraph $S$ of a graph $G$ is a graph such that:
  • The vertices of $S$ are a subset of the vertices of $G$
  • The edges of $S$ are a subset of the edges of $G$
• A spanning subgraph of $G$ is a subgraph that contains all the vertices of $G$
• A graph is connected if there is a path between every pair of vertices
• A tree is an undirected graph $T$ such that
  • $T$ is connected
  • $T$ has no cycles
• A forest is an undirected graph without cycles
• The connected components of a forest are trees

• A spanning tree of a connected graph is a spanning subgraph that has all vertices covered with a minimum possible number of edges
  • A spanning tree is not unique unless the graph is a tree
    • Multiple spanning trees exist
  • Spanning trees have applications in the design of communication networks
  • A spanning forest of a graph is a spanning subgraph that is a forest

Depth First Search

DFS is a general technique for traversing a graph. A DFS traversal of a graph $G$ will:

• Visit all vertices and edges of $G$
• Determine whether $G$ is connected
• Compute the spanning components of $G$
• Compute the spanning forest of $G$

DFS on a graph with $n$ vertices and $m$ edges takes $O(n+m)$ time. The algorithm is:

• For a graph $G$ and a vertex $u$ of $G$
• Mark vertex $u$ as visited
• For each of $u$'s outgoing edges $e=(u,v)$
  • If $v$ has not been visited then
    • Record $e$ as the discovery edge for vertex $v$
    • Recursively call DFS with on $v$

DFS(G,V) visits all vertices and edges in the connected component of v, and the discovery edges labelled by DFS(G,V) form a spanning tree of the connected component of v.

DFS can also be extended to path finding, to find a path between two given vertices $u$ and $v$. A stack is used to keep track of the path, and the final state of the stack is the path between the two vertices. As soon as the destination vertex $v$ is encountered, the contents of the stack is returned.

DFS can be used for cycle detection too. A stack is used to keep track of the path between the start vertex and the current vertex. As soon as a back edge $(v,w)$ (an edge we have already been down in the opposite direction) is encountered, we return the cycle as the portion of the stack from the top to the vertex $w$.

To perform DFS on every connected component of a graph, we can loop over every vertex, doing a new DFS from each unvisited one. This will detect all vertices in graphs with multiple connected components.

Breadth First Search

BFS is another algorithm for graph traversal, similar to DFS. It also requires $O(n+m)$ time. The difference between the two is that BFS uses a stack while DFS uses a queue. The algorithm is as follows:

• Mark all vertices and edges as unexplored
• Create a new queue
• Add the starting vertex $s$ to the queue
• Mark $s$ as visited
• While the queue is not empty
  • Pop a vertex $v$ from the queue
  • For all neighbouts $w$ of $v$
    • If $w$ is not visited
      • Push $w$ into the queue
      • Mark $w$ as visited

For a connected component $G_s$ of graph $G$ containing $s$:

• BFS visits all vertices and edges of $G_s$
• The discovery edges labelled by BFS(G,s) form a spanning tree of $G_s$
• The path of the spanning tree formed by the BFS is the shortest path between the two vertices

BFS can be specialised to solve the following problems in $O(n+m)$ time:

• Compute the connected components of a graph
• Compute a spanning forest of a graph
• Find a simple cycle in G
• Find the shortest path between two vertices
  • DFS cannot do this, this property is unique to BFS

Directed Graphs

A digraph (short for directed graph) is a graph whose edges are all directed.

• Each edge goes in only one direction
• Edge $(a,b)$ goes from a to b but not from b to a
• If the graph is simple and has $n$ vertices and $m$ edges, $m\le n\frac{n-1}{2}$
• DFS and BFS can be specialised to traversing directed edges
  • A directed DFS starting at a vertex $s$ determines the vertices reachable from $s$
  • One vertex is reachable from another if there is a directed path to it

Strong Connectivity

A digraph is said to be strongly connected if each vertex can reach all other vertices. This property can be identified in $O(n+m)$ time with the following algorithm:

• Pick a vertex $v$ in the graph $G$
• Perform a DFS starting from $v$
  • If theres a vertex not visited, return false
• Let $G^{\prime }$ be $G$ with all the edge directions reversed
• Perform a DFS starting from $v$ in $G^{\prime }$
  • If theres a vertex not visited, return false
  • Else, return True

Transitive Closure

Given a digraph $G$, the transitive closure of $G$ is the digraph $G\ast$ such that:

• $G\ast$ has the same vertices as $G$
• If $G$ has a directed path from $u$ to $v$, then G* also has a directed *edge* from $u$ to $v$
• In $G\ast$, every pair of vertices with a path between them in $G$ is now adjacent
• The transitive closure provides reachability information about a digraph

The transitive closure can be computed by doing a DFS starting at each vertex. However, this takes $O(n(n+m))$ time. Alternatively, there is the Floyd-Warshall algorithm:

• For the graph $G$, number the vertices $1,2,...,n$
• Compute the graphs $G_0,...,G_n$
  • $G_0=G$
  • $G_k$ has directed edge $(v_i,v_j)$ if $G$ has a directed path from $v_i$ to $v_j$ with intermediate vertices $v_1,...,v_k$
• Digraph $G_k$ is computed from $G_{k-1}$
• $G_n=G\ast$
• Add $(v_i,v_j)$ if edges $(v_i,v_k)$ and $(v_k,v_j)$ appear in $G_{k-1}$

In pseudocode:

for k=1 to n
    Gk = Gk_1
      for i=1 to n (i != k)
          for j=1 to n (j != i, j!=k)
              if G_(k-1).areAdjacent(vi,vk) && G_(k-1).areAdjacent(vk,vj)
                  if !G_(k-1).areAdjacent(vi,vj)
                      G_k.insertDirectedEdge(vi,vj,k)
  return G_n

This algorithm takes $O(n^3)$ time. Basically, at each iteration a new vertex is introduced, and each vertex is checked to see if a path exists through the newly added vertex. If it does, a directed edge is inserted to transitively close the graph.

Topological Ordering

• A Directed Acyclic Graph (DAG) is digraph that has no directed cycles
• A topological ordering of a digraph is a numbering $v_1,v_2,...,v_n$ of the vertices such that for every edge $(v_i,v_j)$, $i<j$
  • The vertex it points to is always greater than it
• A digraph can have a topological ordering if and only if it is a DAG

A topological ordering can be calculated using a DFS:

public static void topDFS(Graph G, Vertex v){
    v.visited = true
    for(Edge e: v.edges){
        w = opposite(v,e)
        if(w.visited = false)
            topDFS(G,w)
        else{
            v.label = n
            n = n-1
        }
    }
}

The first node encountered in the DFS is assigned $n$, the one after that $n-1$, and so on until all nodes are labelled.

CS132

Note that specifics details of architectures such as the 68k, its specific instruction sets, or the PATP are not examinable. They are included just to serve as examples.

The 68008 datasheet can be found here, as a useful resource.

Digital Logic

Digital logic is about reasoning with systems with two states: on and off (0 and 1 (binary)).

Basic Logic Functions

Some basic logic functions, along with their truth tables.

NOT

$$f=\bar{A}$$

AND

$$f=A\cdot B$$

OR

$$f=A+B$$

XOR

$$f=A\oplus B$$

NAND

$$f=\overline{A\cdot B}$$

NOR

$$f=\overline{A+B}$$

X-NOR

$$f=\overline{A\oplus B}$$

Logic Gates

Logic gates represent logic functions in a circuit. Each logic gate below represents one of the functions shown above.

Logic Circuits

Logic circuits can be built from logic gates, where outputs are logical functions of their inputs. Simple functions can be used to build up more complex ones. For example, the circuit below implements the XOR function.

$$f=\bar{A}\cdot B+A\cdot \bar{B}$$

Another example, using only NAND gates to build XOR. NAND (or NOR) gates can be used to construct any logic function.

Truth tables can be constructed for logic circuits by considering intermediate signals. The circuit below has 3 inputs and considers 3 intermediate signals to construct a truth table.

$$\begin{gathered} P=A\cdot B \\ Q=A\cdot B \\ R=A\cdot C \end{gathered}$$

$$f=P+Q+R=A\cdot B+A\cdot B+A\cdot C$$

Truth tables of circuits are important as they enumerate all possible outputs, and help to reason about logic circuits and functions.

Boolean Algebra

• Logic expressions, like normal algebraic ones, can be simplified to reduce complexity
  • This reduces the number of gates required for their implementation
  • The less gates, the more efficient the circuit is
    • More gates is also more expensive
• Sometimes, only specific gates are available too and equivalent expressions must be found that use only the available gates
• Two main ways to simplify expressions
  • Boolean algebra
  • Karnaugh maps
• The truth table for the expression before and after simplifying must be identical, or you've made a mistake

Expressions from Truth Tables

A sum of products form of a function can be obtained from it's truth table directly.

Taking only the rows that have an output of 1:

• The first row of the table: $\bar{A}\cdot \bar{B}\cdot \bar{C}$
• The second row: $\bar{A}\cdot \bar{B}\cdot C$
• Fifth: $A\cdot \bar{B}\cdot \bar{C}$
• Seventh: $A\cdot B\cdot \bar{C}$
• Eight: $A\cdot B\cdot C$

Summing the products yields:

$$f=(\bar{A}\cdot \bar{B}\cdot \bar{C})+(\bar{A}\cdot \bar{B}\cdot C)+(A\cdot \bar{B}\cdot \bar{C})+(A\cdot B\cdot \bar{C})+(A\cdot B\cdot C)$$

Boolean Algebra Laws

There are several laws of boolean algebra which can be used to simplify logic expressions:

• Can go from AND to OR form (and vice versa) by swapping AND for OR, and 0 for 1

Most are fairly intuitive, but some less so. The important ones to remember are:

• $A+BC=(A+B)(A+C)$
• $A(B+C)=AB+AC$
• $A(A+B)=A$
• $A+AB=A$

De Morgan's Laws

De Morgan's Laws are very important and useful ones, as they allow to easily go from AND to OR. In simple terms:

• Break the negation bar
• Swap the operator

Example 1

When doing questions, all working steps should be annotated.

$$f=(\overline{X+Y})\cdot (\overline{\bar{X}+Y})$$ $$f=(\bar{X}\cdot \bar{Y})\cdot (\overline{\bar{X}+Y})\text{De Morgan OR form}$$ $$f=(\bar{X}\cdot \bar{Y})\cdot (X\cdot \bar{Y})\text{De Morgan AND form}$$ $$f=\bar{X}\cdot \bar{Y}\cdot X\cdot \bar{Y}\text{Remove brackets (associative law)}$$ $$f=\bar{X}\cdot X\cdot \bar{Y}\cdot \bar{Y}\text{Re-order (commutative law)}$$ $$f=0\cdot \bar{Y}\text{Inverse and idempotent laws}$$ $$f=0\text{Null law}$$

Example 2

$$f=X+\bar{Y}+\bar{X}\cdot Y+(X+\bar{Y})\cdot \bar{X}\cdot Y$$ $$f=X+\bar{Y}+\bar{X}\cdot Y+X\cdot \cdot \bar{X}\cdot Y+\bar{Y}\cdot \bar{X}\cdot Y\text{Distributive law}$$ $$f=X+\bar{Y}+\bar{X}\cdot Y+0+0\text{Inverse AND law}$$ $$f=X+(\bar{Y}+\bar{X})(\bar{Y}+Y)\text{Distributive law}$$ $$f=X+(\bar{Y}+\bar{X})\cdot 1\text{Inverse law}$$ $$f=X+\bar{Y}+\bar{X}\text{Removing 1 and brackets (identity and associative laws)}$$ $$f=\bar{Y}+1\text{Inverse OR law}$$ $$f=1\text{Null law}$$

Karnaugh Maps

• Karnaugh Maps (k-maps) are sort of like a 2D- truth table
• Expressions can be seen from the location of 1s in the map

• Functions of 3 variables can used a 4x2 or 2x4 map (4 variables use a 4x4 map)

• Adjacent squares in a k-map differ by exactly 1 variable
  • This makes the map gray coded
• Adjacency also wraps around

The function $f=AB\bar{C}D+A\bar{B}\bar{C}D+\bar{A}\bar{B}CD+\bar{A}BCD$ is shown in the map below.

Grouping

• Karnaugh maps contain groups, which are rectangular clusters of 1s -
• To simplify a logic expression from a k-map, identify groups from it, making them as large and as few as possible
• The number of elements in the group must be a power of 2
• Each group can be described by a singular expression
• The variables in the group are the ones that are constant within the group (ie, define that group)

Sometimes, groups overlap which allow for more than one expression

The function for the map is therefore either $f=\bar{A}\bar{B}\bar{C}+\bar{A}BD+BCD$ or $f=\bar{A}\bar{B}\bar{C}+\bar{A}\bar{C}D+BCD$ (both are equivalent)

Sometimes it is not possible to minimise an expression. the map below shows an XOR function $f=(A\oplus B)\oplus (C\oplus D)$

Don't Care Conditions

Sometimes, a certain combination of inputs can't happen, or we dont care about the output if it does. An X is used to denote these conditions, which can be assumed as either 1 or 0, whichever is more convenient.

Combinatorial Logic Circuits

Some useful circuits can be constructed using logic gates, examples of which are shown below. Combinatorial logic circuits operate as fast as the gates operate, which is theoretically zero time (realistically, there is a nanosecond-level tiny propagation delay).

1-Bit Half Adder

• Performs the addition of 2 bits, outputting the result and a carry bit.

1-Bit Full Adder

• Adds 2 bits plus carry bit, outputting the result and a carry bit.

N-Bit Full Adder

• Combination of a number of full adders
• The carry out from the previous adder feeds into the carry in of the next

N-Bit Adder/Subtractor

• To convert an adder to an adder/subtractor, we need a control input $Z$ such that:
  • $Z=0\Rightarrow S=A+B$
  • $Z=1\Rightarrow S=A-B$
• $-B$ is calculated using two's complement
  • Invert the N bit binary number B by doing $Z\oplus B$
  • Add 1 (make the starting carry in a 1)

Encoders & Decoders

• A decoder has binary input pins, and one output pin per possible input state
• eg 2 inputs has 4 unique states so has 4 outputs
  • 3 inputs has 8 outputs
• Often used for addressing memory
• The decoder shown below is active low
  • Active low means that 0 = active, and 1 = inactive
    • Converse to what would usually be expected
  • Active low pins sometimes labelled with a bar, ie $\overline{\text{enable}}$
• It is important to be aware of this, as ins and outs must comform to the same standard

• Encoders are the opposite of decoders, encoding a set of inputs into outputs
• Multiple input pins, only one should be active at a time
• Active low encoder shown below

Multiplexers & De-Multiplexers

Multiplexers have multiple inputs, and then selector inputs which choose which of the inputs to put on the output.

$$Y=X_0{\bar{S}}_0{\bar{S}}_1+X_1{\bar{S}}_0{S}_1+X_2{S}_0{\bar{S}}_1+X_3{S}_0{S}_1$$

De-Multiplexers are the reverse of multiplexers, taking one input and selector inputs choosing which output it appears on. The one shown below is active low

$$Y_0=A+{\bar{S}}_0{S}_1+S_0{\bar{S}}_1+S_0{S}_1=A+S_1+S_0$$

Multiplexers and De-Multiplexers are useful in many applications:

• Source selection control
• Share one communication line between multiple senders/receivers
• Parallel to serial conversion
  • Parallel input on X, clock signal on S, serial output on Y

Sequential Logic Circuits

A logic circuit whose outputs are logical functions of its inputs and it's current state

Flip-Flops

Flip-flops are the basic elements of sequential logic circuits. They consist of two nand gates whose outputs are fed back to the inputs to create a bi-stable circuit, meaning it's output is only stable in two states.

• $\bar{S}$ and $\bar{R}$ are active low set and reset inputs
• $Q$ is set high when $\bar{S}=0$ and $\bar{R}=1$
• $Q$ is reset (to zero) when $\bar{R}=0$ and $\bar{S}=1$
• If $\bar{S}=\bar{R}=1$ then $Q$ does not change
• If both $\bar{S}$ and $\bar{R}$ are zero, this is a hazard condition and the output is invalid

The timing diagram shows the operation of the flip flop

D-Type Latch

A D-type latch is a modified flip-flop circuit that is essentially a 1-bit memory cell.

• Output can only change when the enable line is high
• $D=Q$ when enabled, otherwise $Q$ does not change ($Q=Q$)
• When enabled, data on $D$ goes to $Q$

Clocked Flip-Flop

There are other types of clocked flip-flop whose output only changes on the rising edge of the clock input.

• $\uparrow$ means rising edge responding

N-bit Register

• A multi-bit memory circuit built up from d-type latches
• The number on $A_{N-1}{A}_{N-2}...A_1{A}_0$ is stored in the registers when the clock rises
• The stored number appears on the outputs $Q$
• $Q$ cannot change unless the circuit is clocked
• Parallel input, parallel output

N-bit Shift Register

• A register that stores and shifts bits taking one bit input at a time
• Serial input, parallel output
• When a clock transition occurs, each bit in the register will be shifted one place
• Useful for serial to parallel conversion

N-bit Counter

• The circles on the clock inputs are inverted on all but the first
• Each flip-flop is triggerd on a high -> low transition of the previous flip-flop
• Creates a counter circuit

Output is 0000, 1000, 0100, 1100, 0010, etc...

• The first bit swaps every clock
• 2nd bit swaps every other clock
• 3rd bit swaps every fourth clock
• etc...

Three State Logic

• Three state logic introduces a third state to logic - unconnected
• A three-state buffer has an enable pin, which when set high, disconnects the output from the input
• Used to prevent connecting outputs to outputs, as this can cause issues (short circuits)

This can be used to allow different sources of data onto a common bus. Consider a 4-bit bus, where 2 4-bit inputs are connected using 3-state buffers. Only one of the buffers should be enabled at any one time.

• When $\overline{E1}=0$, A will be placed on the bus
• When $\overline{E2}=0$, B will be placed on the bus

Physical Implementations

Logic gates are physical things with physical properties, and these have to be considered when designing with them. Typical voltage values for TTL (Transistor-Transistor Logic):

• 5v - max voltage
• 2.8v - minimum voltage for a logical 1
• 2.8-0.8v - "forbidden region", ie voltages in this region are undefined
• 0.8-0v - voltage range for a logical 0

Propagation Delay

• Logic gates have a propagation delay, the amount of time it takes for the output to reflect the input
  • Typically a few nanoseconds or less
• This limits the speed at which logic circuits can operate
• Delay can be reduced by increasing density of gates on an IC

Integrated Circuits

• Elementary logic gates can be obtained in small ICs
• Programmable deviced allow large circuits to be created inside a single chip
  • PAL - Programmable Array Logic
    • One-time programmamble
  • PLA - Programmable Logic Array
    • Contains an array of AND and OR gates to implement any logic functions
  • FPGA - Field Programmable Gate Array
    • Contains millions of configurable gates
    • More modern

PLA example

A PLA allows for the implementation of any sum-of-products function, as it has an array of AND gates, then OR gates, with fuses that can be broken to implement a specific function.

Assembly

Microprocessor Fundamentals

The CPU

• The CPU controls and performs the execution of instructions
• Does this by continuously doing fetch-decode-execute cycle
• Very complex, but two key components
  • Control Unit (CU)
    • Decodes the instructions and handles logistics
  • Arithmetic Logic Unit (ALU)
    • Does maths

Fetch-Decode-Execute

• Three steps to every cycle
  • Fetch instructions from memory
  • Decode into operations to be performed
  • Execute to change state of CPU
• Takes place over several clock cycles

The components of the CPU that are involved in the cycle:

• ALU
• CU
• Program Counter (PC)
  • Tracks the memory address of the next instruction to be executed
• Instruction Register (IR)
  • Contains the most recent instruction fetched
• Memory Address Register (MAR)
  • Contains address of the memory location to be read/written
• Memory Data/Buffer Register (MDR/MBR)
  • Contains data fetched from memory or to be written to memory

The steps of the cycle:

• Fetch
  • Instruction fetched from memory location held by PC
  • Fetched instruction stored in IR
  • PC incremented to point to next instruction
• Decode
  • Retrieved instruction decoded
  • Establish opcode type
• Execute
  • CU signals the necessary CPU components
  • May result in changes to data registers, ALU, I/O, etc

The 68008

The 68008 is an example of a CPU. The "programmer's model" is an abstraction that represents the internals of the architecture. The internal registers as shown below are part of the programmer's model.

• Internal registers are 32 bits wide
• Internal data buses are 16 bit wide
• 8 bit external data bus
• 20 bit external address bus
• D0-D7 are 32 bit registers used to store frequently used values
  • Can be long (32 bits), word (16 bits), or byte (8 bits)
• Status register (CCR) consists of 2 8-bit registers
  • Various status bits are set or reset depending upon conditions arising from execution
• A0-A6 are pointer registers
• A7 is system stack pointer to hold subroutine return addresses
• Operations on addresses do not alter status register/ CCR
  • Only ALU can incur changes in status
• The stack pointer is a pointer to the next free location in the system stack
  • Provides temporary storage of state, return address, registers, etc during subroutine calls and interrupts

The diagram shows the internal architecture of the CPU, and how the internal registers are connected via the buses. Note how and which direction data moves in, as indicated by the arrows on the busses.

Register Transfer Language

The fetch-decode-execute cycle is best described using Register Transfer Language (RLT), a notation used to show how data moves around the internals of a processor and between registers.

• For example [MAR] <- [PC] denotes the transfer of the contents of the program counter to the memory address register
• Computer's main memory is called Main Store (MS), and the contents of memory location N is denoted [MS(N)]
• RLT does not account for the pipelining of instructions
• Fetching an instruction in RTL:

Assembly Language

• Assembly is the lowest possible form of code
• High level code (for example C) is compiled to assembly code
• Assembly is then assembled into machine code (binary)
• Assembly instructions map 1:1 to processor operations
• Uses mnemonics for instructions, ie MOV or ADD
• Languages vary, but format tends to be similar: LABEL: OPCODE OPERAND(S) | COMMENT

An example program is shown below

    ORG  4B0      | this program starts at hex 4B0
    move.b #5, D0  | load D0 with number 5
    add.b  #A, D0 | add 10 (0x0A) to D0
    move.b D0, ANS | move contents of D0 to ANS
ANS: DS.B 1        | leave 1 byte of memory empty and name it ANS

• # indicates a literal
• `` means hexadecimal
• % means binary
• A number without a prefix is a memory address
• ANS is a symbolic name
• ORG (Origin) indicates where to load the program in memory
• DS (Define Storage) tells the assembler where to put data

The 68008 Instruction Set

• Instructions are commands that tell the processor what to do
• 5 main kinds of instructions
  • Logical
    • Bitwise operations
    • AND, LSL (Logical Shift Left)
  • Branch
    • Cause the processor to jump execution to a labelled address
    • Condition is specified by testing state of CCR set by previous instruction
    • BRA - branch unconditionally
    • BEQ - branch if equal
  • System Control
• Instructions are also specified with their data type, .b for byte, .w for word, .l for long
  • move.w moves 2 bytes

Data Movement

• Similar to RTL

move.b D0,   D1 | [D1(0:7)] <- [D0(0:7)]
move.w D0,   D1 | [D1(0:15)] <- [D0(0:15)]
swap   D2       | swap lower and upper words
move.l F20, D3  | [D3(24:31)] ← [MS(<span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.13889em;">F</span><span class="mord">20</span><span class="mclose">)]</span><span class="mord">∣</span><span class="mopen">[</span><span class="mord mathnormal" style="margin-right:0.02778em;">D</span><span class="mord">3</span><span class="mopen">(</span><span class="mord">16</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">:</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">23</span><span class="mclose">)]</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">←</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">[</span><span class="mord mathnormal" style="margin-right:0.05764em;">MS</span><span class="mopen">(</span></span></span></span>F21)]
                | [D3( 8:15)] ← [MS(<span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.13889em;">F</span><span class="mord">22</span><span class="mclose">)]</span><span class="mord">∣</span><span class="mopen">[</span><span class="mord mathnormal" style="margin-right:0.02778em;">D</span><span class="mord">3</span><span class="mopen">(</span><span class="mord">0</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">:</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">7</span><span class="mclose">)]</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">←</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">[</span><span class="mord mathnormal" style="margin-right:0.05764em;">MS</span><span class="mopen">(</span></span></span></span>F23)]
                | copied 8 bytes at a time in big endian order

Arithmetic

• Maths performed on the ALU
• The 68008, like many older processors, has no FPU, so only integer operations are supported

add.l   Di, Dj  | [Dj] ← [Di] + [Dj]
addx.w  Di, Dj  | also add in x bit from CCR
sub.b   Di, Dj  | [Dj] ← [Dj] - [Di]
subx.b  Di, Dj  | also subtract x bit from CCR
mulu.w  Di, Dj  | [Dj(0:31)] ← [Di(0:15)] * [Dj(0:15)]
                | unsigned multiplication
muls.w  Di, Dj  | signed multiplication

Logical

• Perform bitwise operations on data
• Also done by ALU
• AND, OR, etc but also shifts and rotates
• Logical shift (LSL/LSR) adds a 0 when shifting
  • Bit shifted out goes into C and X
• Arithmetic shift preserves sign bit (ASL/ASR)
• Normal rotate (ROL/ROR) moves the top of the bit to the bottom bit and also puts the top bit into C and X
• Rotate through X (ROXL/ROXR) rotates the value through the X register

AND.B #7F, D0 | [D0] <- [D0] . [0x7F]
OR.B  D1,  D0 | [D0] <- [D0] + [D1]
LSL D0,    2  | [D0] <- [D0] << [2]

Branch

• Cause the processor to move execution to a new pointer (jump/GOTO)
• Instruction tests the state of the CCR bits against certain condition
• Bits set by previous instructions

BRA | branch unconditionally
BCC | branch on carry clear
BEQ | branch on equal

System Control

• Certain instructions used to issue other commands to the microprocessor

Subroutines and Stacks

• Subroutines are useful for frequently used sections of code for obvious reasons
• Can jump and return from subroutines in assembly
  • JSR <label> - Jump to Subroutine
  • RTS - Return from Subroutine
• When returning, need to know where to return to
• The stack is used as a LIFO data structure to store return addresses
• JSR pushes the contents of the PC on the stack
• RTS pops the return address from the stack to the PC
• Can nest subroutine calls and stack will keep track

Addressing Modes

• Addressing modes are how we tell the computer where to find the data it needs
• 5 Kinds in the 68006, and many other processors have equivalents
  • Direct
  • Immediate
  • Absolute
  • Address Register Indirect
    • 5 variations
  • Relative

Direct Addressing

• Probably the simplest
• The address of an operand is specified by either a data or address register

move D3, D2 | [D2] <- [D3]
move D3, A2 | [A2] <- [D3]

Immediate Addressing

• The operand forms part of the instruction (is a literal) and remains a constant
• Note the prefix # specifying a literal and the prefix specifying the base of the number

move.b #42, D5 | [D5] <- 42

Absolute Addressing

• Operand specifies the location in memory
• Does not allow for position-independent code: will always access the exact address given

move.l D2, 7FFF0 | [MS(7FFF0)] <- [D2]

Address Register Indirect Addressing

• Uses offsets/increments/indexing to address memory based upon the address registers
• Bad, rarely used
• Not examinable

Relative Addressing

• Specifies an offset relative to the program counter
• Can be used to write position independent code

move 16(PC), D3 | [D3] <- [MS(PC + 16)]

Memory Systems

The Memory Hierarchy

• Memory systems must facilitate the reading and writing of data
• Many factors influence the choice of memory technology
  • Frequency of access
  • Access time
  • Capacity
  • Cost
• Memory wants to be low cost, high capacity, and also fast
• As a tradeoff, we organise memory into a hierarchy
  • Allows for some high speed, some high capacity

• Data has to be dragged up the hierarchy
• Memory access is somewhat predictable
• Temporal locality - when a location accessed, likely the same location will be accessed again in the near future
• Spatial locality - when a location accessed, likely that nearby locations will be referenced in the near future
  • 90% of memory access is within 2Kb of program counter

Semiconductor Memory Types

• Particularly interested in random access
• RAM is most common - implements main store
  • nb that all types shown here allow random access, name is slightly misleading
• RAM is also volatile, meaning it is erased when de powered

Cache

• If 90% of memory access is within 2Kb, store those 2Kb somewhere fast
• Cache is small, fast memory right next to CPU
• 10-200 times faster
• If data requested is found in cache, this is a "cache hit" and provides a big speed improvement
• We want things to be in cache
• Cache speed/size is often a bigger bottleneck to performance than clock speed

Moore's Law

• As said by the co-founder of intel, Gordon Moore, the number of transistors on a chip will double roughly every 18 months
  • Less true in recent years
• Cost of computer logic and circuitry has fallen dramatically in the last 30 years
• ICs become more densely paced
• CPU clock speed is also increasing at a similar rate
• Memory access speed is improving much more slowly however

Cache Concepts

• Caching read-only data is relatively straightforward
  • Don't need to consider the possibility data will change
  • Copies everywhere in the memory hierarchy remain consistent
• When caching mutable data, copies can become different between cache/memory
• Two strategies for maintaining parity
  • Write through - updates cache and then writes through to update lower levels of hierarchy
  • Write back - only update cache, then when memory is replaced copy blocks back from cache

Cache Performance

Cache performance is generally measured by its hit rate. If the processor requests some block of memory and it is already in cache, this is a hit. The hit rate is calculated as

$$h=\frac{\text{total number of cache hits}}{\text{total number of memory accesses}}$$

Cache misses can be categorised:

• Compulsory - misses that would occur regardless of cache size, eg the first time a block is accessed, it will not be in cache
• Capacity - misses that occur because cache is not large enough to contain all blocks needed during program execution
• Conflict - misses that occur as a result of the placement strategy for blocks not being fully associative, meaning a block may have to be discarded and retrieved
• Coherency - misses that occur due to cache flushes in multiprocessor systems

Measuring performance solely based upon cache misses is not accurate as it does not take into factor the cost of a cache miss. Average memory access time is measured as hit time + (miss rate $\times$ miss penalty).

Cache Levels

Cache has multiple levels to provide a tradeoff between speed and size.

• Level 1 cache is the fastest as it is the closest to the cpu, but is typically smallest
  • Sometimes has separate instructions/data cache
• Level 2 cache is further but larger
• Level 3 cache is slowest (but still very fast) but much larger (a few megabytes)
• Some CPUs even have a level 4 cache

Different levels of cache exist as part of the memory hierarchy.

Semiconductors

• RAM memory used to implement main store
• Static RAM (SRAM) uses a flip-flop as the storage element for each bit
  • Uses a configuration of flip-flops and logic gates
  • Hold data as long as power is supplied
  • Provide faster read/write than DRAM
  • Typically used for cache
  • More expensive
• Dynamic RAM (DRAM) uses a capacitor, and the presence to denote a bit
  • Typically simpler design
  • Can be packed much tighter
  • Cheaper to produce
  • Capacitor charge decays so needs refreshing by periodically supplying charge
• The interface to main memory is a critical performance bottleneck

Memory Organisation

The basic element of memory is a one-bit cell with two states, capable of being read and written. Cells are built up into larger banks with combinatorial logic circuits to select which cell to read/write. The diagram shows an example of a 16x8 memory IC (16 words of 8 bytes).

For a 16x8 memory cell:

• 4 address inputs
  • ${\log }_{2}16$
• 8 data lines
  • word size

Consider alternatively a 1Kbit device with 1024 cells

• Organised as a 128x8 array
  • 7 address pins
  • 8 data pins
• Or, could organise as 1024x1 array
  • 10 address pins
  • 1 data pins
• Less pins but very poorly organised
• Best to keep memory cells square to make efficient use of space

Error Correction

Errors often occur within computer systems in the transmission of data dude to noise and interference. This is bad. Digital logic already gives a high degree of immunity to noise, but when noise is at a high enough level, this collapses.

Two common ways in which errors can occur:

• Isolated errors
  • Occur at random due to noise
  • Usually singular incidences
• Burst errors
  • Errors usually occur in bursts
  • A short period of time over which multiple errors occur
  • For example, a 1ms dropout of a connection can error many bits

Majority Voting

• A simple solution to correcting errors
• Just send every bit multiple times (usually 3)
  • The one that occurs the most is taken to be the true value
• Slow & expensive

Parity

• Parity adds an extra parity bit to each byte
• Two types of parity system
  • Even parity
    • The value of the extra bit is chosen to make the total number of 1s an even number
  • Odd parity
    • The value of the extra bit is chosen to make the total number of 1s an odd number
• 7 bit ascii for A is 0100 0001
  • With even parity - 0100 0001
  • Odd parity - 1100 0001
• Can be easily computed in software
• Can also be computed in hardware using a combination of XOR gates
  • Usually faster than in software
• Allows for easy error detection without the need to significantly change the model for communication
• Parity bit is computed and added before data is sent, parity is checked when data is received
• Note that if there is more than one error, the parity bit will be correct still and the error won't be detected
  • Inadequate for detecting bursts of error

Error Correcting Codes

• ECCs or checksums are values computed from the entire data
• If any of the data changes, the checksum will also change
• The checksum is calculated and broadcast with the data so it can be checked on reception
• Can use row/column parity to compute an checksum
  • Calculate parity of each row and of each column
  • Diagram shows how parity bits detect an error in the word "Message"

I/O

Memory Mapped I/O

• With memory mapped I/O, the address bus is used to address both memory and I/O devices
• Memory on I/O devices is mapped to values in the main address space
• When a CPU accesses a memory address, the address may be in physical memory (RAM), or the memory of some I/O device
• Advantages
  • Very simple
  • CPU requires less internal logic
  • Can use general purpose memory instructions for I/O
• Disadvantages
  • Have to give up some memory
    • Less of a concern on 64-bit processors
    • Still relevant in smaller 16 bit CPUs

Polled I/O

• Polling is a technique for synchronising communication between devices.
• Most I/O devices are much slower than the CPU
• Busy-wait polling involves constantly checking the state of the device
  • Usually the device replies with nothing
  • Can interleave polls with something else useful

• Advantages
  • Still relatively simple
• Disadvantages
  • Wastes CPU time and power
  • Interleaving can lead to delayed responses from CPU

Synchronisation methods also need some way to transfer the data, so are sometimes used in conjunction with memory-mapped I/O. Methods for synchronising devices and methods for reading/writing data are not directly comparable.

Handshaking

Another form of synchronisation

• Computer responds to the printer being ready by placing data on the data bus and signalling DATA_VALID
  • Can do this either in hardware or in software
• Timing diagram shows data exchange
• During periods where both signals are at a logical 0, data is exchanged

Handshaking Hardware

Handshaking is usually done using an external chip, such as the 6522 VIA (Versatile Interface Adapter)

Setting bit values in the PCR (Peripheral Control Register) on the VIA allows to control the function.

• Use PORT B as output
• CB1 control line as PRINTER_READY
• CB2 control line as DATA_VALID
• For CB1 and CB2 control, 8 bit register is set to 1000xxxx
  • Last 4 bits not used, don't care

Interrupts

• Asynchronous I/O
• Two kinds of interrupts (in 6502 processor)
  • Interrupt Request (IRQ)
    • Code can disable response
    • Sent with a priority
    • If priority lower than that of current task, will be ignored
    • Can become non-maskable if ignored for long enough
  • Non-Maskable Interrupt (NMI)
    • Cannot be disabled, must be serviced
• An interrupt forces the CPU to jump to an Interrupt Service Routine (ISR)
  • Switches context, uses stack to store state of registers
• ISRs can be nested
• Interrupts usually generated by some external device
  • Hard drive can generate an interrupt when data is ready
  • A timer can generate an interrupt repeatedly at a fixed interval
  • A printer can generate an interrupt when ready to receive data
• Advantages
  • Fast response
  • No wasted CPU time
• Disadvantages
  • All data transfer still CPU controlled
  • More complex hardware/software

Direct Memory Access (DMA)

• The CPU is a bottleneck for I/O
• All techniques shown so far are limited by this bottleneck
• DMA is used where large amounts of data must be transferred quickly
• Control of system busses surrendered from CPU to a DMA Controller (DMAC)
  • DMAC is a dedicated device optimised for data transfer
• Can be up to 10x faster than CPU-driven I/O

DMA Operation

• DMA transfer is requested by I/O
• DMAC passes request to CPU
• CPU initialises DMAC
  • Input or Output?
  • Start address is put into DMAC address register
  • Number of words is put into DMAC count register
  • CPU enables DMAC
• DMAC requests use of system busses
• CPU responds with DMAC ack when ready to surrender busses
• DMAC can operate in different modes
  • Cycle stealing
    • Uses system busses when they're not being used by CPU
  • Burst mode
    • Requires busses for extended period of time, locks the CPU out for a fixed time, until transfer complete, or until CPU receives interrupt from device of higher priority

DMA Organisation

There are multiple ways a DMA can be incorporated into a system:

• Single bus, detached DMA
  • All modules (DMA, I/O devices, memory, CPU) share system bus
  • DMA uses programmed I/O to exchanged data between memory and I/O device
  • Straightforward, as DMA can just mimic processor
  • Inefficient
• Separate I/O bus
  • Only one interface to DMA module
  • The bus the DMA shares with processor and memory is only used to transfer data to and from memory

Summary